Міністерство науки і освіти України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра програмного забезпечення
Звіт з лабораторної роботи №9
з дисципліни “Алгоритми і структури даних ”
Виконав:
студент групи ПІ – 1
Львів 2008
Тема роботи: Ознайомлення із методами пошуку. Алгоритм пошуку в глибину.
Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із методом пошуку в глибину. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу пошуку в глибину.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Пошук в глибину (англ. Depth-first search (DFS)) — один з методів обходу графа. Коротко суть алгоритму можна викласти так: для кожної непройденої вершины необхідно знайти всі непройдені суміжні вершини та повторити пошук для них.
На рис. 1 представлено дерево, вершини якого пронумеровано в порядку обходу цього дерева алгоритмом пошуку в глибину.
Рис. 1. Порядок обходу дерева в глибину.
Текст програми
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
struct S* create(struct S*, struct S*);
void clean(struct S*);
int find(struct S*,int);
/*-Struktura-*/
struct S
{
int a; //Vlasne znachenna
struct S* left; //Vk. na livogo syna
struct S* right; //Vk. na pravogo syna
};
//-----------------------------------
void main()
{
S* ptr;
int a;
clrscr();
ptr=create(
create(
create(
create(
create(
NULL,
create(
create(
NULL,
NULL),
create(
NULL,
create(
NULL,
create(
create(
NULL,
NULL),
create(
NULL,
NULL)))))),
NULL),
create(
NULL,
NULL)),
NULL),
create(
create(
NULL,
NULL),
create(
create(
NULL,
NULL),
create(
create(
NULL,
NULL),
create(
NULL,
NULL)))));
scanf("%i", &a);
printf(find(ptr,a)?"Znajdeno!":"Ne znajdeno!");
clean(ptr);
getch();
}
//------------------------------------
int find(struct S* b,int c)
{
printf("%i\n", b->a);
return (b->a==c ||
b->left!=NULL&&find(b->left,c) ||
b->right!=NULL&&find(b->right,c));
}
/*-Stvorenn'a vershyn vyschyh rivniv-*/
struct S* create(struct S* a, struct S* b)
{
struct S* c=(struct S*)malloc(sizeof(struct S));
c->left=a;
c->right=b;
c->a=rand()%40;
return c;
}
/*-Ochyschenna pam'jati-*/
void clean(struct S* b)
{
if(b->left!=NULL)
delete(b->left);
if(b->right!=NULL)
delete(b->right);
free(b);
}
Протокол роботи програми
Висновок: Вивчив та дослідив метод пошуку, як один із методів обробки даних. Ознайомився із методом пошуку в глибину. Виконав лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу пошуку в глибину.
